package main.Q1_100;

public class Q61_70 {
    public static void main(String[] args) {
        System.out.println("Question61：旋转链表");
        System.out.println("Question62：不同路径");
        System.out.println("Question63：不同路径Ⅱ");
        System.out.println("Question64：最小路径和");
        System.out.println("Question65：");
        System.out.println("Question66：加一");
        System.out.println("Question67：二进制求和");
        System.out.println("Question68：");
        System.out.println("Question69：x的平方根");
        System.out.println("Question70：爬楼梯");
    }
}

class Question61{
    public ListNode rotateRight(ListNode head, int k) {
        if (head==null||k<=0) return head;
        int length=0;
        ListNode last=head,newHead=head;
        while (last!=null&&last.next!=null){//统计链表长度
            last=last.next;
            length++;
        }
        length++;
        while (k>length) k=k-length;
        if (k==length) return head;
        for (int i=0;i<length-k-1;i++){
            newHead=newHead.next;
        }
        ListNode result=newHead.next;
        newHead.next=null;
        last.next=head;
        return result;
    }
}

class Question62{
    public int process(int m,int n,int i,int j){//暴力递归动态规划
        if (i>=m||j>=n) return 0;
        if (i==m-1&&j==n-1) return 1;
        int right=process(m,n,i,j+1);
        int down=process(m,n,i+1,j);
        return right+down;
    }
    public int uniquePaths(int m, int n) {
//        return process(m,n,0,0);
        int[][] dp=new int[m][n];//动态规划表
        for (int i=0;i< dp.length;i++){
            for (int j=0;j<dp[0].length;j++){
                if (i==0||j==0) dp[i][j]=1;//0行0列为1
                else {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

class Question63{
    public int process(int[][] obstacleGrid,int i,int j){//暴力递归动态规划
        if (i>=obstacleGrid.length||j>=obstacleGrid[0].length||obstacleGrid[i][j]==1) return 0;
        if (i==obstacleGrid.length-1&&j==obstacleGrid[0].length-1) return 1;
        int right=process(obstacleGrid,i,j+1);
        int down=process(obstacleGrid,i+1,j);
        return right+down;
    }
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//        return process(obstacleGrid,0,0);
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];
        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }
        return f[m - 1];
    }
}

class Question64{
    public int process(int[][] gird,int row,int col){
        if (row>= gird.length||col>=gird[0].length) return Integer.MAX_VALUE;//越界
        if (row== gird.length-1&&col==gird[0].length-1) return gird[row][col];//终止
        int sum=gird[row][col];
        int right=process(gird, row, col+1);//向右
        int down=process(gird, row+1, col);//向下
        sum+=Math.min(right,down);
        return sum;
    }
    public int minPathSum(int[][] grid) {
//        return process(grid,0,0);//动态规划的递归
        int row= grid.length,col=grid[0].length;
        int[][] dynamicTable=new int[row][col];//动态规划表，普通位置值依赖于上面和左面的最小值加入本身位置的值
        for (int i=0;i< row;i++){
            for (int j=0;j<col;j++){
                if (i==0&&j==0) dynamicTable[0][0]=grid[0][0];//初始位置
                else if (i==0&&j!=0) dynamicTable[i][j]=dynamicTable[i][j-1]+grid[i][j];//第0行
                else if (i!=0&&j==0) dynamicTable[i][j]=dynamicTable[i-1][j]+grid[i][j];//第0列
                else {
                    int min=Math.min(dynamicTable[i-1][j],dynamicTable[i][j-1]);
                    dynamicTable[i][j]=min+grid[i][j];
                }

            }
        }
        return dynamicTable[row-1][col-1];
    }
}

class Question66{
    public int[] plusOne(int[] digits) {
        digits[digits.length-1]+=1;
        int[] result=new int[digits.length+1];
        for (int i= digits.length-1;i>0;i--){
            if (digits[i]>9){//满10进位
                digits[i-1]=digits[i-1]+1;
                digits[i]=digits[i]%10;
            }
        }
        if (digits[0]>9){
            for (int i= digits.length-1;i>0;i--) result[i+1]=digits[i];
            result[1]=digits[0]%10;
            result[0]=digits[0]/10;
            return result;
        }else return digits;
    }
}

class Question67{
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();
        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }
        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();
        return ans.toString();
    }
}

class Question69{
    public int mySqrt(int x) {
        int result=0,left=1,right=x/2;
        if (x==1||x==0) return x;
        while (left<=right){
            int mid=left+(right-left)/2;//防止越界
            if ((long)mid*mid<=x){//防止越界
                result=mid;
                left=mid+1;
            }else right=mid-1;
        }
        return result;
    }
}

class Question70{
    public int climbStairs(int n) {
        int num=0,head=1,end=2,result=0;
        for (int i=3;i<=n;i++){
            result=head+end;
            head=end;
            end=result;
        }
        if (n==1) result=1;
        else if (n==2) result=2;
        return result;
    }
}